Wireless mesh networks are ubiquitous as a cost-effective means to provide broadband connectivity to large user populations. For instance, wireless mesh networks are being deployed in many cities in order to provide ubiquitous Internet access. A mesh network's gateway nodes that connect the wireless mesh with the wired Internet are critical capacity points as their location and quantity determine the maximum throughput supported by the mesh network. Namely, the placement of these gateways determines the hop-length of the paths in the network, the amount of congestion, and the available bandwidth to and from the Internet. As the network usage grows, new gateways need to be added to provide additional available bandwidth capacity (i.e., maximize throughput) to and from the Internet.
Determining the locations to add gateway nodes to maximize capacity is difficult. One of the challenges is that the contention on each gateway depends on the full routing matrix. In addition, a greater amount of contention leads to less available capacity. Thus, each gateway's capacity depends on the locations of other gateways and cannot be known in advance of placing a gateway in a new location. Hence, the available capacity at any given gateway is heavily dependent on where all other gateways are located. For this reason, one gateway cannot be just placed at a time. The process can be time consuming, especially for large mesh networks where contention can be a factor in many locations.